package com.note.feng.leetcode.algorithms.easy.tree;

import java.util.ArrayList;
import java.util.List;

public class FiveHundredThrity {
    /**
     * 530 二叉搜索树的最小绝对差
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     *
     * 差值是一个正数，其数值等于两值之差的绝对值。
     *
     * 示例 1：
     *
     * 输入：root = [4,2,6,1,3]
     * 输出：1
     * 示例 2：
     *
     * 输入：root = [1,0,48,null,null,12,49]
     * 输出：1
     *
     * 提示：
     *
     * 树中节点的数目范围是 [2, 104]
     * 0 <= Node.val <= 105
     *
     * 注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst
     */
    /**
     * 解法：中序遍历
     * 借助二叉搜索树中序遍历特性：得到的数组是升序排列的。
     * 计算相邻两个元素的差值，找到最小的返回即可
     * @param root
     * @return
     */
    public int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        getTreeVal(root, list);
        int diff = list.get(list.size() - 1);
        for (int i = 1; i < list.size(); i++) {
            int d = list.get(i) - list.get(i - 1);
            diff = diff < d ? diff : d;
        }
        return diff;
    }

    private void getTreeVal(TreeNode node, List<Integer> list){
        if(node == null){
            return;
        }
        getTreeVal(node.left, list);
        list.add(node.val);
        getTreeVal(node.right, list);
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
